/**
 *  @file PrintAndFreeInOrder.c
 *  @desc 构造一个带头结点的单链表，按递增顺序输出所有数据元素，并释放结点内存空间（不使用辅助数组）
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-04 10:44
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

// 定义链表结点结构
typedef struct node {
    int data;              // 数据域
    struct node *next;     // 指针域，指向下一个结点
} node, *link;

// 创建一个带指定值的新结点
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;  // 内存分配失败
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// 初始化头结点（带头结点的链表结构）
void initNode(link *head) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return;  // 内存分配失败
    newNode->data = 0;            // ⚠️ 注意：data 是 int，不应该设为 NULL
    newNode->next = NULL;
    *head = newNode;              // 赋值给 head 指针
}

// 尾插法插入新结点
void insertTail(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;  // 创建失败
    link cur = head;              // 从头结点开始
    while (cur->next != NULL) {
        cur = cur->next;          // 遍历到末尾
    }
    cur->next = newNode;          // 插入到末尾
}

// 打印链表（跳过头结点）
void printList(link head) {
    if (head == NULL) return;
    link cur = head->next;        // 从第一个数据结点开始
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

/**
 * @brief 按递增顺序输出链表中的所有数据，并释放结点所占内存
 * @param head 带头结点的链表头指针（不可为 NULL）
 */
void printAndFreeInOrder(link head) {
    if (head == NULL) return;

    // 重复找到最小节点并输出，直到链表为空
    while (head->next != NULL) {
        link cur = head->next;       // 当前结点指针（第一个数据结点）

        link minNode = cur;          // 最小值结点，初始为第一个数据结点
        link minPre = head;          // 最小值结点的前驱指针

        // 遍历链表找最小值结点和其前驱
        while (cur->next) {
            if (cur->next->data < minNode->data) {  // ⚠️ 这里原来写的是 >，逻辑错误，应该是 <
                minPre = cur;
                minNode = cur->next;
            }
            cur = cur->next;
        }

        // 打印最小值
        printf("value is %d\n", minNode->data);

        // 从链表中移除最小值结点
        minPre->next = minNode->next;
        free(minNode);               // 释放该结点内存
    }

        free(head); // 最后释放头结点
}



int main() {
    link head = NULL;

    // 初始化带头结点的链表
    initNode(&head);

    // 向链表插入数据元素
    insertTail(head, 4);
    insertTail(head, 2);
    insertTail(head, 3);

    // 输出链表（按递增顺序）并释放结点
    printAndFreeInOrder(head);

    return 0;
}
